<html><!-- Created using the cpp_pretty_printer from the dlib C++ library.  See http://dlib.net for updates. --><head><title>dlib C++ Library - max_cost_assignment_abstract.h</title></head><body bgcolor='white'><pre>
<font color='#009900'>// Copyright (C) 2011  Davis E. King (davis@dlib.net)
</font><font color='#009900'>// License: Boost Software License   See LICENSE.txt for the full license.
</font><font color='#0000FF'>#undef</font> DLIB_MAX_COST_ASSIgNMENT_ABSTRACT_Hh_
<font color='#0000FF'>#ifdef</font> DLIB_MAX_COST_ASSIgNMENT_ABSTRACT_Hh_

<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='../matrix.h.html'>../matrix.h</a>"
<font color='#0000FF'>#include</font> <font color='#5555FF'>&lt;</font>vector<font color='#5555FF'>&gt;</font>

<font color='#0000FF'>namespace</font> dlib
<b>{</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font><font color='#0000FF'>typename</font> EXP<font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>typename</font> EXP::type <b><a name='assignment_cost'></a>assignment_cost</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> matrix_exp<font color='#5555FF'>&lt;</font>EXP<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> cost,
        <font color='#0000FF'>const</font> std::vector<font color='#5555FF'>&lt;</font><font color='#0000FF'><u>long</u></font><font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> assignment
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - cost.nr() == cost.nc()
            - for all valid i:
                - 0 &lt;= assignment[i] &lt; cost.nr()
        ensures
            - Interprets cost as a cost assignment matrix. That is, cost(i,j) 
              represents the cost of assigning i to j.  
            - Interprets assignment as a particular set of assignments. That is,
              i is assigned to assignment[i].
            - returns the cost of the given assignment. That is, returns
              a number which is:
                sum over i: cost(i,assignment[i])
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font><font color='#0000FF'>typename</font> EXP<font color='#5555FF'>&gt;</font>
    std::vector<font color='#5555FF'>&lt;</font><font color='#0000FF'><u>long</u></font><font color='#5555FF'>&gt;</font> <b><a name='max_cost_assignment'></a>max_cost_assignment</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> matrix_exp<font color='#5555FF'>&lt;</font>EXP<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> cost
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - EXP::type == some integer type (e.g. int)
              (i.e. cost must contain integers rather than floats or doubles)
            - cost.nr() == cost.nc()
        ensures
            - Finds and returns the solution to the following optimization problem:

                Maximize: f(A) == assignment_cost(cost, A)
                Subject to the following constraints:
                    - The elements of A are unique. That is, there aren't any 
                      elements of A which are equal.  
                    - A.size() == cost.nr()

            - This function implements the O(N^3) version of the Hungarian algorithm 
              where N is the number of rows in the cost matrix.
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
<b>}</b>

<font color='#0000FF'>#endif</font> <font color='#009900'>// DLIB_MAX_COST_ASSIgNMENT_ABSTRACT_Hh_
</font>

</pre></body></html>